Feature detection is an important process used in image processing, for example in computer vision. One particular type of feature detection is that of corner detection, which may be used to determine the outline of an object in a scene captured by an imaging device such as a camera.
The FAST (Features from Accelerated Segment Test) algorithm, described for example in E. Rosten, T. Drummond, “Machine learning for high-speed corner detection”, European Conference on Computer Vision, 2006, pp. 430-443, is a known feature/corner detection algorithm used in computer vision as it is efficient to run on some processor-architectures. Depending on the particular processor architecture, it can be many times faster than other existing corner detectors. It also offers high levels of repeatability with large aspect changes and for different kinds of feature.
The FAST algorithm (FAST9 variant) will now be explained with reference to FIG. 1, in which a region of pixels from an image is shown. The FAST algorithm operates on the basis of a Bresenham circle of pixels Pi (where 15>=i>=0) about a centre pixel Pc
Based on this Bresenham circle of pixels, the FAST algorithm applies a criterion to determine a corner. This criteria is that a candidate corner is a corner if there are N contiguous pixels such that Pi>Pc+T or Pi<Pc−T for each pixel Pi in the contiguous arc, where T is threshold, suitably predefined. N may be 9, 10, 11 or 12. Any of the patterns in the figure below would produce a correct output from the FAST detector. Similar patterns exist for other FAST variants such as FAST7, FAST12 etc.
The method may employ Non-Maximal suppression as an additional test to confirm a corner. In this additional test, each corner is given a score based on the absolute sum of the differences between each pixel Pi in the arc and the centre pixel. This score may be used to suppress non-maximum corners in a close knit group.
Whilst the FAST algorithm is useful, it has its limitations. For example, whilst it may be employed readily within Scalar/RISC processor architectures, implementation on SIMD/VLIW processor architectures is relatively poor as the number of cycles/pixel can be high due to the overhead of branch delay slots due to the high number of pixel comparisons as detection requirements increase.
In addition to software implementations of the FAST algorithm a relevant hardware implementation is presented in Vilariño, D. L., Brea, V. M., “Feature detection and matching on an SIMD/MIMD hybrid embedded processor”, Computer Vision and Pattern Recognition Workshops (CVPRW), 2012 IEEE Computer Society Conference on Date of Conference: 16-21 Jun. 2012, pp. 21-26 which has a performance of 88 CC/Pixel per processing element on proposed efficient architecture (128 PEs on FPGA). While interesting this architecture is dedicated to FAST and the hardware coprocessor is not programmable and neither is the hardware usable for other applications.
The present application addresses this and other problems.